#include <iostream>
#include <vector>
using namespace std;

const int MAXSIZE = 505;
const int INF = 99999;
vector<int> pre[MAXSIZE], path, temp;
int c, n, sp, m, s[MAXSIZE], graph[MAXSIZE][MAXSIZE], minneed = INF, minremain = INF;

void Dijkstra(int g[][MAXSIZE], int v, int n)
{
    int set[MAXSIZE], dist[MAXSIZE];
    int min, i, j, u;
    for (i = 0; i < n; i++)
    {
        dist[i] = g[v][i];
        set[i] = 0;
        if (g[v][i] < INF)
            pre[i].push_back(v);
        else
            pre[i].push_back(-1);
    }
    set[v] = 1;
    pre[v].push_back(-1);
    for (i = 0; i < n - 1; i++)
    {
        min = INF;
        for (j = 0; j < n; j++)
        {
            if (set[j] == 0 && dist[j] < min)
            {
                u = j;
                min = dist[j];
            }
        }
        set[u] = 1;
        for (j = 0; j < n; ++j)
        {
            if (set[j] == 0 && dist[u] + g[u][j] < dist[j])
            {
                dist[j] = dist[u] + g[u][j];
                pre[j].clear();
                pre[j].push_back(u);
            }
            else if (dist[u] + g[u][j] == dist[j])
            {
                pre[j].push_back(u);
            }
        }
    }
}
void dfs(int v)
{
    temp.push_back(v);
    if (v == 0)
    {
        int needbike = 0, remainbike = 0;
        for (int i = temp.size() - 2; i >= 0; --i)
        {
            if (s[temp[i]] >= c / 2)
            {
                remainbike += s[temp[i]] - c / 2;
            }
            else
            {
                int x = c / 2 - s[temp[i]];
                if (remainbike > 0)
                {
                    if (remainbike >= x)
                    {
                        remainbike -= x;
                    }
                    else
                    {
                        needbike += x - remainbike;
                        remainbike = 0;
                    }
                }
                else
                {
                    needbike += x;
                }
            }
        }

        if (minneed > needbike)
        {
            minneed = needbike;
            minremain = remainbike;
            path = temp;
        }
        else if (minneed == needbike && minremain > remainbike)
        {
            minneed = needbike;
            minremain = remainbike;
            path = temp;
        }
        temp.pop_back();
        return;
    }
    for (int i = 0; i < pre[v].size(); i++)
    {
        dfs(pre[v][i]);
    }
    temp.pop_back();
}
int main()
{

    int i, j, k, tmp;
    cin >> c >> n >> sp >> m;
    for (i = 0; i <= n; ++i)
        for (j = 0; j <= n; ++j)
            graph[i][j] = INF;
    for (i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    for (i = 0; i < m; ++i)
    {
        cin >> j >> k >> tmp;
        graph[j][k] = graph[k][j] = tmp;
    }

    Dijkstra(graph, 0, n + 1);
    dfs(sp);

    printf("%d ", minneed);
    for (i = path.size() - 1; i >= 0; i--)
    {
        if (i == path.size() - 1)
        {
            cout << path[i];
        }
        else
        {
            cout << "->" << path[i];
        }
    }
    printf(" %d",minremain);
    return 0;
}